package lib

//link to 1953
func init() {
	Probs = append(Probs, Problem{
		Num:         621,
		Discription: "相同任务的冷却期为n,执行完所有任务的最少时间",
		Level:       2,
		Labels: map[string]int{
			"贪心": 1,
		},
	})
}

func LeastInterval(tasks []byte, n int) int {
	taskCount := make(map[byte]int, 0)
	maxCount := 1
	for _, task := range tasks {
		taskCount[task]++
		maxCount = max(maxCount, taskCount[task])
	}

	//执行数量最多的任务需要的最少时间：为什么要-1:之后匹配到相同任务时，+1加回去了
	minTime := (maxCount-1)*n + maxCount - 1
	for _, count := range taskCount {
		//如果再来一个同样是最大数量的任务，在之前的空位中交错插入执行就行，最后多出来一个+1
		if count == maxCount {
			minTime++
		}

		//如果比执行数量比最大任务数小，在这个区间内肯定有插入的地方满足冷却时间n
	}

	////len(tasks)是把空位插满的情况
	return max(minTime, len(tasks))
}